//
//  145. 二叉树的后序遍历.swift
//  手撕code
//
//  Created by xiaoZuDeMeng on 2024/3/6.
//

import Foundation

//https://leetcode.cn/problems/binary-tree-postorder-traversal/description/
//给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
//
//
//
//示例 1：
//
//
//输入：root = [1,null,2,3]
//输出：[3,2,1]
//示例 2：
//
//输入：root = []
//输出：[]
//示例 3：
//
//输入：root = [1]
//输出：[1]
//
//
//提示：
//
//树中节点的数目在范围 [0, 100] 内
//-100 <= Node.val <= 100
//
//
//进阶：递归算法很简单，你可以通过迭代算法完成吗？

//二叉树的后序遍历：按照访问左子树——右子树——根节点的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。

//链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/1125221/dfsmo-ban-fa-shi-xian-er-cha-shu-xian-xu-lbq8/

func 二叉树的后序遍历(_ root: TreeNode?) -> [Int] {
    var postOrderAry = [Int]()
    postOrder(root:root, arr:&postOrderAry)
    return postOrderAry
}

private func postOrder(root:TreeNode?, arr:inout [Int]) {
    guard root != nil else {
        return
    }
    postOrder(root: root!.left, arr: &arr)
    postOrder(root: root!.right, arr: &arr)
    arr.append(root!.val)
}
